// https://leetcode.cn/problems/valid-sudoku/

// 题干：请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
//       数字 1-9 在每一行只能出现一次。
//       数字 1-9 在每一列只能出现一次。
//       数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

// 示例：输入：board =
//  [["5","3",".",".","7",".",".",".","."]
//   ["6",".",".","1","9","5",".",".","."]
//  [".","9","8",".",".",".",".","6","."]
//  ["8",".",".",".","6",".",".",".","3"]
//  ["4",".",".","8",".","3",".",".","1"]
//  ["7",".",".",".","2",".",".",".","6"]
//  [".","6",".",".",".",".","2","8","."]
//  [".",".",".","4","1","9",".",".","5"]
//  [".",".",".",".","8",".",".","7","9"]]
//      输出：true

// 碎语：一样是如何剪枝的问题，哈希表的思想，对于行，由于要判断那个数字存不存在，再开一个数组
//       对于3*3的表格剪枝问题，则把它合成一个表格用下标来判断
//       即bool row[9][10] // 多开一个格子，刚好对应
//       bool col[9][10]
//       bool grid[3][3][10]
//       可能作为剪枝的方案

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        // 本质上使用空间换时间
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        memset(grid, 0, sizeof(grid));

        bool test = true;
        for (int i = 0 ; i < 9 ; i++){ // 行数
            for (int j = 0 ; j < 9 ; j++){ // 列数
                if (board[i][j] == '.') continue;
                else {
                    int digit = board[i][j] - '0';
                    if (!row[i][digit] && !col[j][digit] && !grid[i / 3][j / 3][digit]){
                        row[i][digit] = true, col[j][digit] = true, grid[i / 3][j / 3][digit] = true;
                    }
                    else test = false;
                }
            }
        }

        return test;
    }
};

int main()
{
    Solution sol;
    vector<vector<char>> board = {
            {'5','3','.','.','7','.','.','.','.'},
            {'6','.','.','1','9','5','.','.','.'},
            {'.','9','8','.','.','.','.','6','.'},
            {'8','.','.','.','6','.','.','.','3'},
            {'4','.','.','8','.','3','.','.','1'},
            {'7','.','.','.','2','.','.','.','6'},
            {'.','6','.','.','.','.','2','8','.'},
            {'.','.','.','4','1','9','.','.','5'},
            {'.','.','.','.','8','.','.','7','9'}
    };

    cout << sol.isValidSudoku(board) << endl;

    return 0;
}